Dijkstra Prize

The Edsger W. Dijkstra Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade. The prize has been presented annually since 2000.

Originally the prize was presented at the ACM Symposium on Principles of Distributed Computing (PODC), and it was known as the PODC Influential-Paper Award. It was renamed in honor of Edsger W. Dijkstra in 2003, after he received the award for his work in self-stabilization in 2002 and died shortly thereafter.

Since 2007,[1] the prize is sponsored jointly by PODC and the EATCS International Symposium on Distributed Computing (DISC), and the presentation takes place alternately at PODC (even years) and DISC (odd years). The prize includes an award of $2000.

Contents

Winners

Year Paper Topic
2000[2] Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system". Communications of the ACM 21 (7): 558–565. doi:10.1145/359545.359563. http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf.  edit Lamport logical clock
2001[3] Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "Impossibility of distributed consensus with one faulty process". Journal of the ACM 32 (2): 374–382. doi:10.1145/3149.214121. http://theory.lcs.mit.edu/tds/papers/Lynch/jacm85.pdf.  edit Proving the impossibility of consensus using asynchronous communication
2002 Dijkstra, E. W. (November 1974). "Self-stabilizing systems in spite of distributed control". Communications of the ACM 17 (11): 643-644. doi:10.1145/361179.361202.  edit Self-stabilization
2003[4] Herlihy, M. (1991). "Wait-free synchronization". ACM Transactions on Programming Languages and Systems 13 (1): 124–149. doi:10.1145/114005.102808.  edit Maurice Herlihy Solvability and universality of consensus in shared-memory systems
2004[5] Gallager, R. G.; Humblet, P. A.; Spira, P. M. (1983). "A Distributed Algorithm for Minimum-Weight Spanning Trees". ACM Transactions on Programming Languages and Systems 5 (1): 66–77. doi:10.1145/357195.357200.  edit Distributed algorithm to find a minimum spanning tree
2005[6] Pease, M.; Shostak, R.; Lamport, L. (April 1980). "Reaching Agreement in the Presence of Faults". Journal of the ACM 27 (2): 228–234. doi:10.1145/322186.322188.  edit Byzantine agreement
2006 Mellor-Crummey, J. M.; Scott, M. L. (1991). "Algorithms for scalable synchronization on shared-memory multiprocessors". ACM Transactions on Computer Systems 9 (1): 21–65. doi:10.1145/103727.103729.  edit "probably the most influential practical mutual exclusion algorithm of all time"[7]
2007[8] Dwork, C.; Lynch, N.; Stockmeyer, L. (1988). "Consensus in the presence of partial synchrony". Journal of the ACM 35 (2): 288–323. doi:10.1145/42282.42283.  edit Solving consensus in partially synchronous systems
2008[9] Awerbuch, B.; Peleg, D. (1990). "Sparse partitions". Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. pp. 503–513. doi:10.1109/FSCS.1990.89571. ISBN 0-8186-2082-X.  edit Sparse partitions
2009 Halpern, J. Y.; Moses, Y. (1990). "Knowledge and Common Knowledge in a Distributed Environment". Journal of the ACM 37 (3): 549–587. doi:10.1145/79147.79161.  edit A formal framework for reasoning about knowledge in distributed systems
2010 Chandra, T. D.; Toueg, S. (1996). "Unreliable Failure Detectors for Reliable Distributed Systems". Journal of the ACM 43 (2): 225-267. doi:10.1145/226643.226647.  edit
Chandra, T. D.; Hadzilacos, V.; Toueg, S. (1996). "The Weakest Failure Detector for Solving Consensus". Journal of the ACM 43 (4): 685-722. doi:10.1145/234533.234549.  edit		 Failure detectors
2011 Attiya, H.; Bar-Noy, A.; Dolev, D. (1995). "Sharing Memory Robustly in Message-Passing Systems". Journal of the ACM 42 (1): 124-142. doi:10.1145/200836.200869.  edit Simulating shared memory in fault-prone message-passing systems

Funding

The award is financed by ACM PODC and EATCS DISC, each providing an equal share of $1,000 towards the $2,000 of the award.

See also

Notes

  1. ^ Calls for nominations: 2005, 2006. DISC 2007 proceedings and web site.
  2. ^ "PODC Influential Paper Award: 2000", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/influential/2000.html, retrieved 2009-08-24 
  3. ^ "PODC Influential Paper Award: 2001", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/influential/2001.html, retrieved 2009-08-24 
  4. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2003", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2003.html, retrieved 2009-08-24 
  5. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2004", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2004.html, retrieved 2009-08-24 
  6. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2005", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2005.html, retrieved 2009-08-24 
  7. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2006", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2006.html, retrieved 2009-08-24 
  8. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2007", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2007.html, retrieved 2009-08-24 
  9. ^ "Edsger W. Dijkstra Prize in Distributed Computing: 2008", ACM Symposium on Principles of Distributed Computing, http://www.podc.org/dijkstra/2008.html, retrieved 2009-08-24 

References